package com.zklh.leetcode.tree.middle;

/**
 * 不同的二叉搜索树算法实现
 * 思路： 动态规划  依据 f(n) = f(n-1) * 1 + f(n-2) * f(1) + f(n-3) * f(2) ... + f(2) * f(n-3) + f(1) + f(n-2) + 1 * f(n-1) 实现
 *
 */
public class Solution96 {
    public int numTrees(int n) {
        // 定义用于存储结果的容器， tables[n] = numsTrees（n）的结果
        int[] tables = new int[n+1];
        tables[0] = 1;
        for(int i = 1; i <= n; i++) {
            // 临时存储的 用于计算 tables[i] 的值
            int result = 0;
            for(int j = 0; j < i; j++) {
                result += tables[j] * tables[i-j-1];
            }
            tables[i] = result;
        }
        return tables[n];
    }

    public static void main(String[] args) {
        Solution96 solution = new Solution96();
        System.out.println(solution.numTrees(3));
    }
}
